package cn.leonis.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author Tobi
 * @Date 2021-12-12 下午12:50
 * 在线选举
 * leetcode911
 */
public class OnlineElectionSolution {


}

class TopVotedCandidate {
    List<Integer> tops;
    Map<Integer, Integer> voteCounts;
    int[] times;

    public TopVotedCandidate(int[] persons, int[] times) {
        tops = new ArrayList<>();
        voteCounts = new HashMap<>();
        voteCounts.put(-1, -1);
        int top = -1;
        for (int i = 0; i < persons.length; i++) {
            int p = persons[i];
            voteCounts.put(p, voteCounts.getOrDefault(p, 0) + 1);
            if (voteCounts.get(p) >= voteCounts.get(top)) {
                top = p;
            }
            tops.add(top);
        }

        this.times = times;
    }

    public int q(int t) {
        int left = 0, right = times.length - 1;
        while (left < right) {
            int middle = left + (right - left + 1) / 2;
            if (times[middle] <= t) {
                left = middle;
            } else {
                right = middle - 1;
            }
        }
        return tops.get(left);
    }
}
